/***************************************************************************
 * 
 * Copyright (c) 2012 Baidu.com, Inc. All Rights Reserved
 * common.h,v 1.0 2012-08-22 15:39 yelu01
 * 
 **************************************************************************/
 
 
 
/**
 * @file bloom_filter.h
 * @author yelu01(yelu01@baidu.com)
 * @date 2012-08-22 10:25
 * @version 1.0 
 * @brief An implementation of bloom filter. On a false positive probability of
 * 0.01, it needs about 1G memory to hold about 10,0000,0000 keys. The following
 * implementation limit the maximum memory to be 1G, so if the optimal memory
 * exceeds 1G, the false positive probability will increase and bigger than you
 * give when constructing a bloom filter.
 * @thread safety: Not safe. But if you only call may_contain() to query whether
 * a key exist or not after the bloom filter has been created and all elements
 * has been inserted, it is thread safe and lock free.
 *  
 **/

#pragma once

#include <cstdlib>
#include <vector>
#include "hash_func.h"
#include "log.h"
#include "check_macro.h"

class bloom_filter_t
{
public:
	bloom_filter_t();
	virtual ~bloom_filter_t();
	int create(uint64_t nkeys = 1024, double pf = 0.01);
	int insert(const void* key, uint32_t key_len);
	bool may_contain(const void* key, uint32_t key_len);
	uint64_t serialize(FILE* fp);
	uint64_t deserialize(FILE* fp);

private:
	// generate _num_hashfuncs seeds for the only one hash function, so that
	// it seems we have _num_hashfuncs distinct hash functions.
	void _generate_hash_seeds();

	// gen optimal parameters.
	int _calc_optimal_params();

	// calc indics of the bit arr.
	void _calc_bit_idx(uint64_t hash, uint64_t& byte_idx, uint32_t& bit_idx);

	// num of bits used. why using uint64_t? max unit32_t bits consumes 512M,
	// when _num_keys exceeds 1,0000,0000, this is not enough.
	uint64_t _num_bits;
	uint64_t _num_keys;	// how many keys estimated.
	uint32_t _num_hashfuncs;	// how many hash functions needed.
	double _pf;			// probability of false alarm
						// (key not exist but report exist.)
	char* _byte_arr;	// for storing data(contain set and unset bits).
	std::vector<uint32_t> _seeds;
};


